Chapter 2 Section 1 part 1 (2.1.1) - Counting in Decimal, Binary, and Hexadecimal 1. finite number of bits to encode a number unix>p26.sh more p26.c #include main() { int i=200, j=300, k = 400, l = 500; printf("%i\n", i*j*k*l); } gcc p26.c ./a.out -884901888 unix> unix>./p26b.sh more p26b.c #include main() { short i=30000, j=-4000, k; if (i>j) printf("i is greater than j\n"); else printf("i is not greater than j\n"); if ( i-j > 0 ) printf("i is greater than j\n"); else printf("i is not greater than j\n"); k = i-j; if ( k > 0 ) printf("i is greater than j\n"); else printf("i is not greater than j\n"); } gcc p26b.c ./a.out i is greater than j i is greater than j i is not greater than j unix> 2. Base 10 counting 1. Making payments with the United States currency system involves a bit of calculation. For example, if you withdraw $37 from your bank, the teller will probably give you one $20, one $10, one $5, and two $1's. 2. We could simply the tellers job by converting to a "base 10" currency system where each denomination has 10 times the value of the prevous denomination so that the available bills are $1, $10, $100, $1000, $10,000, $100,000 etc. 3. If you withdraw $37 in "base 10" land, the teller would simply give you three $10 bills and seven $1 bills. 4. We will abbreviate "three $10 bills and seven $1 bills" as 37 (base 10). Similarly, if you withdrew $1234 from the bank, you would receive one $1000 bill, two $100 bills, three $10 bills, and four $1 bills, or 1234 (base 10). 3. Base 2 counting 1. In "base 2" land, the available bills are $1, $2, $4, $8, $16, $32 etc. If you withdraw $37 from the bank, the teller would give you one $32, no $16's, no $8's, one $4, no $2's, and one $1 or 100101 (base 2) because 1*32 + 0*16 + 0*8 + 1*4 + 0*2 + 1*1 = 37. 2. Each 0 or 1 in a number like 100101 (base 2) is called a BInary digiT or a bit and the base 2 counting system is called the binary counting system. 3. Notice that 37 (base 10) = 100101 (base 2) in the sense that you don't care if you are paid with three $10's and seven $1's (in the land of base 10) or one $32, one $4, and one $1 (in the land of base 2). Either way, you have the purchasing power of 37 one-dollar bills. 4. In the same way, 1234 (base 10) = 10011010010 (base 2) because $1024 + $128 + $64 + $16 + $2 equals $1234. 4. Quiz - You should now be able to do the following. 1. Convert 500 (base 10) to ______ (base 2) 2. Convert 10101010 (base 2) to ______ (base 10) 3. Convert 155.247.166.60 (the IP address of www.temple.edu) into four (base 2) numbers. 4. Convert 255 (base 2) to ______ (base 10). 5. Base 2 approximations. 1. How many different 3-digit decimal numbers are there? The smallest is 000, the largest is 999 so there are 1000. Similarly, there are 10 million different 7-digit decimal numbers. Note that 10**3 = 1000 and and 10**7 = 10 million. In general, there are 10**n different n-digit decimal numbers. 2. By a similar argument, there are 2 different 1-bit binary numbers. 4 different 2-bit binary numbers 8 different 3-bit binary numbers 64 different 6-bit binary numbers 256 different 8-bit binary numbers 1024 different 10-bit binary numbers 65,536 different 16-bit binary numbers 2**n different n-bit binary numbers. 3. Up to 10 bits, simply count on your fingers - 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. 4. Beyond 10 bits, we use an approximation - 2**10 or 1024 is approximately equal to 1000 or 1k. Remembering that (2**x)*(2**y) = 2**(x+y) 2**16 = (2**6)*(2**10) ~ (64)*(1000) = 64,000 or 64k 2**24 = (2**4)*(2**10)*(2**10) ~ (16)*(1000)*(1000) or 16 million 5. Quiz questions. All answers should be actual numbers (e.g. one billion) not formulas (e.g. 2**30). 1. If the 8-bits in a byte are used to represent integers, how many different integers can be represented. 2. If the 8-bits in a byte are used to store non-negative integers (beginning with zero), what is the largest decimal integer that can be represented. 3. If a c compiler uses 4 bytes (32 bits) to store an unsigned int, what (approximately) is the largest decimal integer that can be stored. 4. The original 1981 IBM PC used an Intel 8088 processor. In 8088 systems, each byte of memory was assigned a unique 20-bit address. What limit did this place on the size of memory (maximum number of bytes of memory). 5. The U.S. government limited certain types of encrpytion keys (passwords) to 40 bits. How many keys would you have to test to "break the code" on a message that used a 40-bit encryption key? 6. An IP address like 155.247.166.60 is just a sequence of four 8-bit bytes where each byte has been converted to a decimal number between 0 and 255. If each computer on the Internet needed a unique IP address, what is the maximum number of computers that could be connected to the Internet. 6. Base 2 addition 1. If you withdrew 10101101 (base 2) from you checking account and 111001 (base 2) from you saving account, what bills (in the base 2 system) should the teller give you. In other words, compute the sum of 10101101 (base 2) and 111001 (base 2). 2. The hard way 1. 10101101 (base 2) = 128 + 32 + 8 + 4 + 1 = 173 (base 10) 2. 111001 (base 2) = 32 + 16 + 8 + 1 = 57 (base 10) 3. 173 (base 10) + 57 (base 10) = 230 (base 10) 4. 230 (base 10) = 128 + 64 + 32 + 4 + 2 = 11100110 (base 2) 3. The easy way step 1 step 2 step 3 step 4 step 5 step 6 1 1 1 1 1 1 10101101 10101101 10101101 10101101 10101101 10101101 + 111001 + 111001 + 111001 + 111001 + 111001 + 111001 --------- --------- --------- --------- --------- --------- 2 0 10 110 2110 0110 step 7 step 8 step 9 step 10 step 11 step 12 1 1 11 1 11 1 111 1 111 1 111 1 10101101 10101101 10101101 10101101 10101101 10101101 + 111001 + 111001 + 111001 + 111001 + 111001 + 111001 --------- --------- --------- --------- --------- --------- 20110 00110 300110 100110 1100110 11100110 4. Quiz questions 1. Compute 10101011 (base 2) + 01001111 (base 2) = _ _ _ _ _ _ _ _ (base 2) 2. Multiply 11010 (base 2) by 110 (base 2). Do the arithmetic (and leave the result) in base 2. Do not convert to base 10 except to check your answer. 3. Subtract 101 (base 2) from 101000 (base 2). 4. To check your answers, fire up Windows and click on Start -> Accessories -> Calculator -> View -> Scientific, and use the Dec and Bin buttons. 8. Hexadecimal counting 1. Base 16 counting system - a country that uses $1, $16, $256, $4096, $65,535 ... dollar bills. 1234 (base 16) = one $4096, two $256, three $16, and four $1 or 4096 + 512 + 68 + 4 = 4680 (base 10). 2. Problem. $47 = two $16 bills and fifteen $1 bills. Can't represent this as 215 (base 16) because that represents two $256 dollar bills, one $16 bill, and five $1 bills or $533. 3. Solution - use "digits" 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F where A (base 16) = 10 (base 10), B (base 16) = 11 (base 10), ..., F (base 16) = 15 (base 10). So $47 (base 10) equals two $16 bills and fifteen $1 bills = 2F (base 16). 4. Decimal, Binary, and Hexadecimal counting decimal binary hex decimal binary hex 0 0000 0 8 1000 8 1 0001 1 9 1001 9 2 0010 2 10 1010 A 3 0011 3 11 1011 B 4 0100 4 12 1100 C 5 0101 5 13 1101 D 6 0110 6 14 1110 E 7 0111 7 15 1111 F 5. Quiz questions 1. Count from 0 (base 16) to 20 (base 16). (Hint - 33 numbers total) 2. Count from 0 (base 3) to 1000 (base 3). (hint - 28 numbers total) 1. Convert A3B (base 16) to (base 10). 2. Convert 555 (base 10) to (base 16). 3. Convert A3B (base 16) to (base 2). 4. Convert 1010111100000111 (base 2) to (base 16). 5. Convert 1234 (base 5) to (base 10). 6. Convert 100 (base 10) to (base 3). 7. Compute 1 + F (base 16). 8. Compute 1 + 1F9 (base 16). 9. Compute 1 + 19F (base 16). 10. Compute 1 + 9FF (base 16). 11. B&O Practice Problem 2.1, 2.2, 2.3, 2.4 9. Hex addition. 1. Use two "yardsticks" labeled in hex. seven equals 13 v v 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15 16 17 19 19 1A ... 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 ... ^ plus C 2. Do away with the yardsticks and use your finters and logic. 1. 4 + 8 (base 16) = 3 + 9 (base 16) = 2 + A (base 16) = 1 + B (base 16) = C 2. 8 + E (base 16) = 7 + F (base 16) = 6 + 10 (base 16) = 16 (base 16). 3. F + F (base 16) = E + 10 (base 16) = 1E (base 16). 4. A + A (base 16) = 10 + 10 (base 10) = 20 (base 10) = 14 (base 16) 3. Quiz questions 1. Add 123 (base 16) and 456 (base 16), answer in base 16. 2. Add 123 (base 16) and ABC (base 16), answer in base 16. 3. Add 456 (base 16) and ABC (base 16), answer in base 16. 3. Add ABC (base 16) and DEF (base 16), answer in base 16. 4. Add 123 (base 5) and 234 (base 5), answer in base 5.